#include <stdio.h>
#include <stdlib.h>
//定义3个全局数组
int A[10000][10000]={0};//A[][]用于存放原始数据，
int B[10000][10000]={0};//B[][]用于存放前面3个数中的最小的一个和该位置对应A中的值的和
int C[10000][10000]={0};//存放最小能量线的路径
int D[10000]={0};//存放能量线的值
int M=10000,N=10000;//定义全局变量
struct TU//定义结构体
{
   int num;
   int h;
   int z;
   struct TU *next;
};
typedef struct TU NODE;
NODE *head1=NULL,*head2=NULL;//分别存储竖直能量线和水平能量线的值

NODE *creat(int k)//创建长度为k的链表
{
    NODE *head=NULL,*tail=NULL,*p=NULL;
    int i=0;
    while(i<3*k)//链表创建结束的标志为i=k
    {
        p=(NODE*)malloc(sizeof(NODE));
        p->num=D[i];//将数组D中的数值赋给链表结点的数据域
        p->h=D[i+1];
        p->z=D[i+2];
        if(head==NULL)
        {
            head=p;
        }
        else
        {
            tail->next=p;
        }
        tail=p;
        i=i+3;
    }
    return head;
}

void print1(int n,int m)
{
    NODE *p;
    p=head1;
    int i=0;
    while(i<(n-1)*m)
    {
        p=p->next;
        i++;
    }
    if(p==NULL) printf("输入错误\n");
    i=0;
    while(i<m)
    {
        printf("%d(%d,%d) ",p->num,p->h,p->z);
        p=p->next;
        i++;
    }
    printf("\n");
};
void print2(int n,int m)
{
    NODE *p;
    p=head2;
    int i=0;
    while(i<(n-1)*m)
    {
        p=p->next;
        i++;
    }
    if(p==NULL) printf("输入错误\n");
    i=0;
    while(i<m)
    {
        printf("%d(%d,%d) ",p->num,p->h,p->z);
        p=p->next;
        i++;
    }
    printf("\n");
};
int minof3(int a,int b,int c)//比较3个数的大小，输出较小的一个
{
	if(a<=b && a<=c)
		return a;
	else if(b<=c)
		return b;
	else
		return c;
}
//找到相邻的三个数，从相邻三个数中取出最小的一个
int getMin1(int i,int j)//找竖直能量线的
{
	int a1,a2,a3;
	if(j-1>=0)//如果左上角相邻的数存在，赋值给a1，否则赋值给a1一个很大的数，以免影响比较大小
		a1=B[i-1][j-1];
	else
		a1=256;
	a2=B[i-1][j];//直接将正上方一个数赋值给a2
	if(j+1<N)
		a3=B[i-1][j+1];//如果右上角相邻的数存在，赋值给a1，否则赋值给a1一个很大的数，以免影响比较大小
	else
		a3=256;
	int min=minof3(a1,a2,a3);//输出相邻三个数中较小的一个
	if(min==a1)
		C[i][j]=-1;//记录-1，意味上一个数来自左上角
	else if(min==a2)
		C[i][j]=0;//记录0，意味上一个数来自正上方
	else
		C[i][j]=1;//记录1，意味上一个数来自右上方
	return min;
}
int getMin2(int i,int j)//找横直能量线
{
	int a1,a2,a3;
	if(i-1>=0)//如果左上角相邻的数存在，赋值给a1，否则赋值给a1一个很大的数，以免影响比较大小
		a1=B[i-1][j-1];
	else
		a1=256;
	a2=B[i][j-1];//直接将正左方一个数赋值给a2
	if(i+1<M)
		a3=B[i+1][j-1];//如果左下角相邻的数存在，赋值给a1，否则赋值给a1一个很大的数，以免影响比较大小
	else
		a3=256;
	int min=minof3(a1,a2,a3);//输出相邻三个数中较小的一个
	if(min==a1)
		C[i][j]=-1;//记录-1，意味上一个数来自左上角
	else if(min==a2)
		C[i][j]=0;//记录0，意味上一个数来自正左方
	else
		C[i][j]=1;//记录1，意味上一个数来自右下角
	return min;
}

void fp1()//找竖直能量线的
{
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			B[i][j]=A[i][j];//将A中的值给B
		}
	}
	for(int i=1;i<M;i++)//B中的第一行数组不变，从第二行开始储存当前数据与上一个最小数的和
	{
		for(int j=0;j<N;j++)
		{
			B[i][j]=getMin1(i,j)+B[i][j];//B等于当前数据与上一个最小数的和，B中最后一行的数据为各条能量线的值之和，最小的值则为所求能量线的值之和
		}
	}
}
void fp2()//找横直能量线的
{
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			B[i][j]=A[i][j];//将A中的值给B
		}
	}
	for(int j=1;j<N;j++)//B中的第一列数组不变，从第二列开始储存当前数据与上一个最小数的和
	{
		for(int i=0;i<M;i++)
		{
			B[i][j]+=getMin2(i,j);//B等于当前数据与上一个最小数的和，B中最后一列的数据为各条能量线的值之和，最小的值则为所求能量线的值之和
		}
	}
}

void printA(int n)//输出竖直能量线的位置，n为能量线的第几条
{
	for(int i=0;i<M;i++)
	{
	    printf("      ");
		for(int j=0;j<N;j++)
		{
		    if(A[i][j]==-1)//如果A[i][j]等于-1，则输出第几条的标志
			printf("  |*Ver%d*|",n);
			else printf("%10d",A[i][j]);//输出数据
		}
		printf("\n");//换行
	}
}
void printB()//输出删除能量线后的数据
{
    for(int i=0;i<M;i++)
    {
        for(int j=0;j<N;j++)
        printf("%10d",A[i][j]);
    printf("\n");
    }
}
void move1()//向左移动数组
{
    for(int i=0;i<M;i++)
    {
        for(int j=0;j<N;j++)
        {
               if(A[i][j]==-1)//如果A[i][j]=-1,则从此位置起数组向左移动一个位置
                {
                    while(j<N)//移动数据的个数
                    {
                    A[i][j]=A[i][j+1];
                    j++;
                    }
                    break;//移动完第一行的数据，结束本行查找，查找下一行的数据
                }
        }
    }
}
void move2()//向上移动数组
{
    for(int j=0;j<N;j++)
    {
        for(int i=0;i<M;i++)
        {
               if(A[i][j]==-1)//如果A[i][j]=-1,则从此位置起数组向上移动一个位置
                {
                    while(i<M)//移动数据的个数
                    {
                    A[i][j]=A[i+1][j];
                    i++;
                    }
                    break;//移动完第一列的数据，结束本列查找，查找下一列的数据
                }
        }
    }
}
void printTrace1(int n,int m)//竖直能量线的标志化，n为最后一个能量线数据的纵坐标
{
    m--;
	D[m-2]=A[M-1][n];//将能量线的值赋给数组D
	D[m-1]=M-1;
	D[m]=n;
	A[M-1][n]=-1;//能量线上的值全部置为-1，作为标志
	int j=n+C[M-1][n];//上一个能量线数据的位置
	for(int i=M-2;i>=0;i--)//i为横坐标
	{
	    m=m-3;;
		D[m-2]=A[i][j];//将能量线的值赋给数组D
		D[m-1]=i;
		D[m]=j;
		A[i][j]=-1;//能量线上的值全部置为-1，作为标志
		j=C[i][j]+j;//上一个能量线数据的位置
	}
}
void printTrace2(int n,int m)//水平能量线的标志化，n为最后一个能量线数据的横坐标
{
    m--;
    D[m-2]=A[n][N-1];//将能量线的值赋给数组D
    D[m-1]=n;
    D[m]=N-1;
    A[n][N-1]=-1;//能量线上的值全部置为-1，作为标志
	int i=n+C[n][N-1];//上一个能量线数据的位置
	for(int j=N-2;j>=0;j--)//j为纵坐标
	{
	    m=m-3;
		D[m-2]=A[i][j];//将能量线的值赋给数组D
		D[m-1]=i;
		D[m]=j;
		A[i][j]=-1;//能量线上的值全部置为-1，作为标志
		i=C[i][j]+i;//上一个能量线数据的位置
	}
	printf("\n");
}
int getResult1()//竖直能量线最后一位数据坐标的查找
{
	int min=256,mini;//min为最小值
	for(int i=0;i<N;i++)//i为纵坐标
	{
		if(B[M-1][i]<min)
		{
			min=B[M-1][i];
			mini=i;
		}//在数组B中最后一行查找最小值，最小值则为最小能量线之和

	}
	printf("min cost:%d\n",min);
	return mini;//最小值的纵坐标
}

int getResult2()//水平能量线最后一位数据坐标的查找
{
	int min=256,mini;//min为最小值
	for(int i=0;i<M;i++)//i为横坐标
	{
		if(B[i][N-1]<min)
		{
			min=B[i][N-1];
			mini=i;
		}//在数组B中最右一行查找最小值，最小值则为最小能量线之和

	}
	printf("min cost:%d\n",min);
	return mini;//最小值的横坐标
}

int main()
{
    printf("=======================================================================================================================\n");
    printf("                    -    *************************           **     **                          -\n");
    printf("                    -    *************************          **     **                           -\n");
    printf("                    -    **       **            **         ***    ***********                   -\n");
    printf("                    -    **      ***            **        ****   *************                  -\n");
    printf("                    -    **     ************    **     * ** **  **         **                   -\n");
    printf("                    -    **    *************    **     ***  ** **    ***********                -\n");
    printf("                    -    **   **         **     **          ** *   ***************              -\n");
    printf("                    -    **  *****     **       **          **     **     **    **              -\n");
    printf("                    -    **  **  **** **        **          **     **************  *      *     -\n");
    printf("                    -    **      ******         **          **        ** **      **      **     -\n");
    printf("                    -    **     **    ****      **          **      **   *****   **     **      -\n");
    printf("                    -    **   **  **     ***    **          **     **   **  *************       -\n");
    printf("                    -    **  ** *   **     ***  **          **         **       ******          -\n");
    printf("                    -    ** ** **    **      ** **          **        **       **   ****        -\n");
    printf("                    -    ** *   **    *      *  **          **               **    **           -\n");
    printf("                    -    **       *             **          **             **     **            -\n");
    printf("                    -    *************************          **                   **             -\n");
    printf("                    -    *************************          **               ****               -\n");
    printf("                    -          **                                                               -\n");
    printf("                    -         ** **********                                                     -\n");
    printf("                    -        ** ************   **           *******    *******************      -\n");
    printf("                    -       *****          **  **           *******    *******************      -\n");
    printf("                    -   ** ** ***           ** **              **      **      **       **      -\n");
    printf("                    -    ***   ***          ** **              **      *******************      -\n");
    printf("                    -           ***        **  **              **      *******************      -\n");
    printf("                    -            ***      **   **              **      **      **       **      -\n");
    printf("                    -              **   **     **              **      *******************      -\n");
    printf("                    -               *****      **           *******    *******************      -\n");
    printf("                    -               ** **      ***          *******            **               -\n");
    printf("                    -              **   **     ****            **              **               -\n");
    printf("                    -             **     **    ** **           **      *******************      -\n");
    printf("                    -            **       **   **              ** **   *******************      -\n");
    printf("                    -           **         **  **              ****            **               -\n");
    printf("                    -          **           *****             ****             **               -\n");
    printf("                    -      ** **              *** *          ***       *******************      -\n");
    printf("                    -      ****                ****         **         *******************      -\n");
    printf("======================================================================================================================\n");
    printf("\n");
    printf("                    *****************************************************************************\n");
    printf("\n");
    printf("                                               图像缩小处理欢迎你!\n");
    printf("                                                请选择你的操作\n");
    printf("\n");
    printf("                    *****************************************************************************\n");
    printf("                                              1.原始图像的输入\n");
    printf("                                              2.目标图像的大小输入\n");
    printf("                                              3.删除竖直能量线\n");
    printf("                                              4.删除水平能量线\n");
    printf("                                              5.能量线值的查找\n");
    printf("                                              6.屏幕的清空\n");
    printf("                                              7.结束操作\n");
    printf("                    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
    int t=-1;
    while(t!=7)
    {
        int a,b,m,n,h1=0,h2=0,h3=0;//a,b为目标图像的大小
        printf("请选择：\n");
        scanf("%d",&t);
        switch(t)
        {
        case 1:
            {
            printf("请输入原始图像的大小:\n");
            scanf("%d%d",&m,&n);
            M=m;
            N=n;
            if(M>0&&N>0) printf("输入成功\n");
            else printf("输入失败\n");
            printf("请输入原始图像的像素:\n");
            int i,j,k=1;
                 for(i=0;i<M;i++)
             for(j=0;j<N;j++)
            scanf("%d",&A[i][j]);
              for(i=0;i<M;i++)
               {
                   for(j=0;j<N;j++)
                    if(A[i][j]<0||A[i][j]>255)//判别输入值是否符合要求
                   {
                       k=0;
                       break;
                   }
               }
               if(k==0) printf("输入失败\n");
               else printf("输入成功\n");
            }
            break;
        case 2:
            {
                printf("请输入目标图像的大小:\n");
                scanf("%d%d",&a,&b);
                if(a>M||b>N||a<1||b<1) printf("输入失败\n");//判别输入值是否符合要求
                else printf("输入成功\n");
            }
            break;
        case 3:
            {
            int i,j=0,s;
             for(i=N;i>b;i--)//计算删除的条数
              {
                j++;//记录第几条
              fp1();//找能量线
              printf("\n");
              printf("第%d条竖直能量线的位置\n",j);
	          int scol1=getResult1();
	          s=3*j*M;//m为每条能量线放入数组D中的第一个数据坐标
	          printTrace1(scol1,s);//将数据放入数组D中，标志
              printA(j);//输出能量线的位置
              move1();//移动
              N--;//删除
              printf("删除第%d条竖直能量线后的图像\n",j);
              printB();//输出删除后的数据
             }
             h1=1;
             h3=1;
            head1=creat(j*M);
            }
            break;
        case 4:
            {
               int i,j=0,s;
            for(i=M;i>a;i--)//计算删除的条数
	          {
              j++;//第几条
	          fp2();//找能量线
	          printf("\n");
	          printf("第%d条水平能量线的位置\n",j);
	          int scol2=getResult2();
              s=3*j*N;//m为每条能量线放入数组D中的第一个数据坐标
	          printTrace2(scol2,s);//将数据放入数组D中，标志
	          printA(j);//输出能量线的位置
	          move2();//移动
	          M--;//删除
	          printf("删除第%d条水平能量线后的图像\n",j);
	          printB();//输出删除后的数据
	          }
	          h2=1;
	          h3=2;
              head2=creat(j*N);
            }
            break;
        case 5:
            {
                int c=1;
              printf("1.竖直能量线的值 2.水平能量线的值 3.结束能量线值的查找\n请输入查找的能量线\n");
              if(h1==1&&h2==1&&h3==1) m=M;
              else if(h1==1&&h2==1&&h3==2) n=N;
              printf("%d %d %d %d",m,M,n,N);
              m=M;n=N;
              printf("%d %d\n",m,n);
              while(c!=3)
              {
              printf("请选择：\n");
              scanf("%d",&c);
              switch(c)
              {
              case 1:
                  {
                int i;
                printf("请输入查找第几条竖直能量线：\n");
                scanf("%d",&i);
                print1(i,m);
                  }
               break;
              case 2:
                  {
                int i;
                printf("请输入查找第几条水平能量线：\n");
                scanf("%d",&i);
                print2(i,n);
                  }
                break;
              }
              }
           }
           break;
           case 6: system("cls"); break;
        }
    }
    return 0;
}
